/*file:hash.cpp
 */

#include <cmath>
#include <cstdlib>
#include <cstring>
#include "hash.h"

using namespace std;

namespace misc {

static const unsigned int HASH_TABLE_MIN_SIZE = 11;
static const unsigned int HASH_TABLE_MAX_SIZE = 13845163;

static const unsigned int g_primes[] =
{
    11,
    19,
    37,
    73,
    109,
    163,
    251,
    367,
    557,
    823,
    1237,
    1861,
    2777,
    4177,
    6247,
    9371,
    14057,
    21089,
    31627,
    47431,
    71143,
    106721,
    160073,
    240101,
    360163,
    540217,
    810343,
    1215497,
    1823231,
    2734867,
    4102283,
    6153409,
    9230113,
    13845163,
};

static const unsigned int g_nprimes = sizeof (g_primes) / sizeof (g_primes[0]);

unsigned int GHashTable::g_spaced_primes_closest (unsigned int num)
{
    unsigned int i;

    for (i = 0; i < g_nprimes; i++)
        if (g_primes[i] > num)
            return g_primes[i];

    return g_primes[g_nprimes - 1];
}

unsigned int g_str_hash (const void *key)
{
    const char *p = static_cast<const char *> (key);
    unsigned int h = *p;

    if (h)
        for (p += 1; *p != '\0'; p++)
            h = (h << 5) - h + *p;

    return h;
}

bool g_str_equal (const void *v1, const void *v2)
{
    const char *string1 = static_cast<const char *> (v1);
    const char *string2 = static_cast<const char *> (v2);

    return strcmp (string1, string2) == 0;
}

GHashTable::GHashTable(GHashFunc hashfc, GEqualFunc keyequalfc)
{
    unsigned int i;

    size               = HASH_TABLE_MIN_SIZE;
    nnodes             = 0;
    hash_func          = hashfc != NULL ? hashfc : g_str_hash;
    key_equal_func     = keyequalfc;
    //this.key_destroy_func   = key_destroy_func;
    //this.value_destroy_func = value_destroy_func;
    nodes              = (GHashNode **)malloc (sizeof(GHashNode *) * size);

    for (i = 0; i < size; i++)
        nodes[i] = NULL;
}

GHashTable::~GHashTable()
{
    unsigned int i;
    for (i = 0; i < size; i++)
        g_hash_nodes_destroy (nodes[i]); 
    free(nodes);
}

GHashNode** GHashTable::g_hash_table_lookup_node (const void *key)
{
    GHashNode **node;

    node = &nodes[(* hash_func) (key) % size];

    /* Hash table lookup needs to be fast.
     *  We therefore remove the extra conditional of testing
     *  whether to call the key_equal_func or not from
     *  the inner loop.
     */
    if (key_equal_func != NULL)
        while (*node && !(*key_equal_func) ((*node)->key, key))
            node = &(*node)->next;
    else
        while (*node && (*node)->key != key)
            node = &(*node)->next;

    return node;
}

void inline GHashTable::g_hash_table_resize ()
{
    if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) || 
            (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE)) {
        GHashNode **new_nodes;
        GHashNode *node;
        GHashNode *next;
        unsigned int hash_val;
        unsigned int new_size;
        unsigned int i;

        new_size = g_spaced_primes_closest (nnodes);
        new_size = (new_size > HASH_TABLE_MAX_SIZE) ? HASH_TABLE_MAX_SIZE : 
            ((new_size < HASH_TABLE_MIN_SIZE) ? HASH_TABLE_MIN_SIZE : new_size);

        new_nodes = (GHashNode **)malloc(sizeof(GHashNode*) * new_size);
        memset(new_nodes, 0, sizeof(GHashNode*) * new_size);

        for (i = 0; i < size; i++) {
            for (node = nodes[i]; node; node = next) {
                next = node->next;

                hash_val = (* hash_func) (node->key) % new_size;

                node->next = new_nodes[hash_val];
                new_nodes[hash_val] = node;
            }
        }

        free (nodes);
        nodes = new_nodes;
        size = new_size;
    }
}

GHashNode* GHashTable::g_hash_node_new (void *key, void *value)
{
    GHashNode *hash_node;

    hash_node = (GHashNode *)malloc(sizeof(GHashNode));
    memset(hash_node, 0, sizeof(GHashNode));

    hash_node->key = key;
    hash_node->value = value;
    hash_node->next = NULL;

    return hash_node;
}

void GHashTable::g_hash_node_destroy (GHashNode *hash_node)
{
    //hash_node->next = node_free_list;
    //node_free_list = hash_node;
    free(hash_node);
}

void GHashTable::g_hash_nodes_destroy (GHashNode *hash_node)
{
    if (NULL != hash_node) {
        GHashNode *node = hash_node;
        GHashNode *freenode = hash_node;

        while(NULL != node->next) {
            freenode = node;
            node = node->next;
            free(freenode);
        }
        free(node);
    }
}

/**
 * g_hash_table_lookup:
 * @key: the key to look up.
 * 
 * Looks up a key in a #GHashTable.
 * 
 * Return value: the associated value, or %NULL if the key is not found.
 **/
void * GHashTable::g_hash_table_lookup (const void *key)
{
    GHashNode *node;

    node = *g_hash_table_lookup_node (key);

    return node ? node->value : NULL;
}

/**
 * g_hash_table_insert:
 * @key: a key to insert.
 * @value: the value to associate with the key.
 * 
 * Inserts a new key and value into a #GHashTable.
 * 
 * If the key already exists in the #GHashTable its current value is replaced
 * with the new value. If you supplied a @value_destroy_func when creating the 
 * #GHashTable, the old value is freed using that function. If you supplied
 * a @key_destroy_func when creating the #GHashTable, the passed key is freed 
 * using that function.
 **/
void GHashTable::g_hash_table_insert (void *key, void *value)
{
    GHashNode **node;

    node = g_hash_table_lookup_node (key);

    if (*node)
    {
        /* do not reset node->key in this place, keeping
         * the old key is the intended behaviour. 
         * g_hash_table_replace() can be used instead.
         */

        /* free the passed key */
        /*if (key_destroy_func)
            key_destroy_func (key);

        if (hash_table->value_destroy_func)
            hash_table->value_destroy_func ((*node)->value);*/

        (*node)->value = value;
    }
    else
    {
        *node = g_hash_node_new (key, value);
        nnodes++;
        g_hash_table_resize ();
    }
}

/**
 * g_hash_table_remove:
 * @key: the key to remove.
 * 
 * Removes a key and its associated value from a #GHashTable.
 *
 * If the #GHashTable was created using g_hash_table_new_full(), the
 * key and value are freed using the supplied destroy functions, otherwise
 * you have to make sure that any dynamically allocated values are freed 
 * yourself.
 * 
 * Return value: %TRUE if the key was found and removed from the #GHashTable.
 **/
bool GHashTable::g_hash_table_remove (const void *key)
{
    GHashNode **node, *dest;

    node = g_hash_table_lookup_node (key);
    if (*node)
    {
        dest = *node;
        (*node) = dest->next;
        g_hash_node_destroy (dest); 
        nnodes--;

        g_hash_table_resize ();

        return true;
    }

    return false;
}


//unsigned int hash(void *k)
//{
//    /* Aim to protect against poor hash functions by adding logic here
//     * - logic taken from java 1.4 GHashTable source */
//    unsigned int i;// = hashfn(k);
//    i += ~(i << 9);
//    i ^=  ((i >> 14) | (i << 18)); /* >>> */
//    i +=  (i << 4);
//    i ^=  ((i >> 10) | (i << 22)); /* >>> */
//    return i;
//}

}//namespace misc

